#pragma once

#include <vector>

namespace jianzhi_033
{

class Solution
{
public:
    bool verifyPostorder(const std::vector<int>& postorder)
    {
        return is_postorder(postorder, 0, postorder.size() - 1);
    }
private:
    bool is_postorder(const std::vector<int>& postorder, int left, int right)
    {
        if (left >= right)
            return true;
        int lsub = right - 1;
        while (lsub >= left && postorder.at(lsub) > postorder.at(right))
            --lsub;

        for (int i = lsub; i >= left; --i) {
            if (postorder.at(i) >= postorder.at(right))
                return false;
        }

        return is_postorder(postorder, left, lsub) &&
               is_postorder(postorder, lsub + 1, right - 1);
    }
};

}  /* namespace jianzhi_033 */
